package com.yinanxi.cool.dws

import scala.collection.mutable.ListBuffer

/**
 * @Created by Orion
 * @Description
 *             遍历树 :统计树某个节点下所有的子节点个数
 *
 *             统计每个节点的子节点
 */

case class Node(url:String ,children:ListBuffer[Node] )
object TestTree {

  def main(args: Array[String]): Unit = {
    // 构建树
    val m = Node("/m" , null)
    val x1 = Node("/x" , null)
    val x2 = Node("/x" , null)
    val y = Node("/y" , ListBuffer[Node](x2))
    val d = Node("/d" , ListBuffer[Node](x1 , y))
    val b1 = Node("/b" , ListBuffer[Node](d))
    val p = Node("/p" , null)
    val o = Node("/o" ,  ListBuffer[Node](p))
    val b2 = Node("/b" , ListBuffer[Node](o))
    val c2 = Node("/c" ,null)
    val a2 = Node("/a" ,ListBuffer[Node](c2))
    val c1 = Node("/c" ,ListBuffer[Node](b2,a2))
    val a1  = Node("/a" ,ListBuffer[Node](m , b1 , c1))


    val buf = ListBuffer[(String, Int)]()
    folowPv2(a1 , buf)

    buf.foreach(println)

  }

  /**
   * 返回当前节点的所有子节点个数
   * @param node
   * @return
   */
  def  folowPv(node: Node) :Int={
    var pv = 0
    val children = node.children
    if (children != null && children.size > 0){
      pv+=children.size
      // 遍历所有的子节点
      for (elem <- children) {
        pv+=folowPv(elem)
      }
    }
    pv
  }

  /**
   * 获取当前节点 和 所有子节点的个数
   * 节点    个数
   * a  12
   * b  4
   * d  3
   * y  1
   */
  def  folowPv2(node: Node , buffer: ListBuffer[(String , Int)]) :Int={
    var pv = 0
    val children = node.children
    if (children != null && children.size > 0){
      pv+=children.size
      // 遍历所有的子节点
      for (elem <- children) {
        pv+=folowPv2(elem , buffer)
      }
    }
    // 将当前节点的地址和子节点个数存储在缓存中
    buffer.append((node.url , pv))
    pv
  }

}
